When time-series signals, such as audio signals and video information, are transmitted on a communication channel or recorded on an information recording medium, it is effective in terms of transmission efficiency or recording efficiency to transmit or record the time-series signals after they are converted to compressed codes. In recent years, increasing use of broadband access and increasing capacity of storage devices have caused greater importance to lossless compression encoding methods that allow the original signal to be reproduced losslessly, rather than lossy compression encoding methods that place the highest priority on high compression rates (refer to non-patent literature 1, for example). In such circumstances, a predictive coding has been approved as an international standard of Moving Picture Experts Group (MPEG), which is named as MPEG-4 ALS (see Non-patent literature 2, for example).
FIG. 1 is a block diagram for illustrating a functional configuration of an encoder 2100 based on a conventional lossless compression encoding scheme. FIG. 2 is a block diagram for illustrating a functional configuration of a residual coding unit 2120 shown in FIG. 1. FIG. 3 is a block diagram for illustrating a functional configuration of a decoder 2200 based on the conventional lossless compression encoding scheme. FIG. 4 is a block diagram for illustrating a functional configuration of a residual decoding unit 2220 shown in FIG. 3. First, the conventional lossless compression encoding scheme will be described with reference to these drawings.
(Encoding Method)
Pulse code modulation (PCM) time-series signals x(n) that are sampled and quantized are input to a frame buffer 2111 in the encoder 2100 (the character n denotes an index representing a discrete time). The frame buffer 2111 buffers time-series signals x(n) (n=0, . . . , N−1, where the character N denotes a positive integer) in a predetermined time segment (referred to as a “frame” hereinafter). The one frame of time-series signals x(n) (n=0, . . . , N−1) buffered is fed into a linear prediction analyzer 2112 in a prediction coding unit 2110, and the linear prediction analyzer 2112 calculates first-order to M-th-order PARCOR coefficients k(m) (m=1, 2, . . . , M) by linear prediction analysis.
The linear prediction analysis is based on the assumption that a linear combination of a time-series signal x(n) at a time n and M time-series signals x(n−1), x(n−2), . . . , x(n−M) at times n−1, n−2, . . . , n−M preceding the time n weighted with coefficients α(m) (m=1, . . . , M) represents a prediction residual e(n) (the character M denotes a “prediction order”, the coefficient α(m) is referred to also as a “linear prediction coefficient”, and the prediction residual e(n) is referred to also as a “prediction error”). A linear prediction model based on the assumption is expressed by the following formula (1). In the linear prediction analysis, for the input one frame of time-series signals x(n) (n=0, . . . , N−1), the linear prediction coefficients α(m) (m=1, . . . , M) that minimize the energy corresponding to the prediction residuals e(n) (n=0, . . . , N−1) for the one frame or other coefficients that can be converted into the linear prediction coefficients α(m), such as PARCOR coefficients k(m) (m=1, . . . , M), are calculated.e(n)=x(n)+α(1)·x(n−1)+α(2)·x(n−2)+ . . . +α(M)·x(n−M)  (1)
Specific examples of the linear prediction analysis include sequential methods, such as the Levinson-Durbin method and the Burg method, and methods of solving, for each prediction order, the simultaneous equations whose solutions are linear prediction coefficients that minimize the prediction residuals, such as the autocorrelation method and the covariance method.
A linear finite impulse response (FIR) filter expressed by the following formula for estimating a time-series signal y(n) at a time n from M time-series signals x(n−1), x(n−2), . . . , x(n−M) at times n−1, n−2, . . . , n−M preceding the time n is referred to as a “linear prediction filter”.Y(n)=−{α(1)·x(n−1)+α(2)·x(n−2)+ . . . +α(M)·x(n−M)}  (2)
The calculated PARCOR coefficients k(m) (m=1, . . . , M) are fed into a quantizer 2113. The quantizer 2113 quantizes the M PARCOR coefficients k(m) (m=1, . . . , M) to generate M quantized PARCOR coefficients i(m) (m=1, . . . , M) and outputs the quantized PARCOR coefficients i(m). For example, to generate a 4-bit quantized PARCOR coefficient i(m) from the PARCOR coefficient k(m), the possible range of the PARCOR coefficient k(m) is divided into 16 sub-ranges, and each of the 4-bit values “0000” to “1111” is assigned to a different one of the 16 sub-ranges. Then, the 4-bit value assigned to the sub-range corresponding to the input PARCOR coefficient k(m) is output as the quantized PARCOR coefficient i(m). The M quantized PARCOR coefficients i(m) (m=1, . . . , M) are fed into a coefficient coding unit 2114, and the coefficient coding unit 2114 generates a coefficient code Ck corresponding to the M quantized PARCOR coefficients i(m) (m=1, . . . , M). The coefficient coding unit 2114 may generate the coefficient code Ck by performing variable length coding of the M quantized PARCOR coefficients i(m) and combining the resulting M codes or by performing variable length coding of a bit sequence composed of the M quantized PARCOR coefficients i(m) (m=1, . . . , M), for example. Alternatively, the coefficient code Ck may be the bit sequence composed of the M quantized PARCOR coefficients i(m) (m=1, . . . , M). In this case, the coefficient coding unit 2114 can be omitted, and the quantizer 2113 can output the coefficient code Ck. The quantized PARCOR coefficients i(m) (m=1, . . . , M) are also fed into a linear prediction coefficient converter 2115. Using these coefficients, the linear prediction coefficient converter 2115 calculates the linear prediction coefficients α(m) (m=1, 2, . . . , M). In general, the linear prediction coefficient converter 2115 determines M PARCOR coefficients k′(m) (m=1, . . . , M) by inverse quantization of the M quantized PARCOR coefficients i(m) (m=1, . . . , M) and then determines the M linear prediction coefficients α(m) (m=1, . . . , M) from the M PARCOR coefficients k′(m) (m=1, . . . , M). The inverse quantization of the quantized PARCOR coefficient i(m) is to determine a predetermined value k′(m) of the PARCOR coefficient k(m) in the sub-range for the quantized PARCOR coefficient i(m). For example, if the quantized PARCOR coefficient i(m) is the quantized value of the PARCOR coefficient k(m) within η1≦k(m)<η2 the PARCOR coefficient k′(m) generated by inverse quantization of the quantized PARCOR coefficient i(m) is the average of η1 and η2, for example.
Using the one frame of time-series signals x(n) (n=0, . . . , N−1) and the linear prediction coefficients α(m) (m=1, . . . , M), a linear prediction unit 2016 generates the linear prediction values y(n) (n=1, . . . , N−1) with the linear prediction filter. A subtractor 2117 calculates the prediction residuals e(n) by subtracting the linear prediction values y(n) from the time-series signals x(n), respectively (a prediction filter processing).
The calculated prediction residuals e(n) are values represented by integers in a predetermined range. For example, suppose that the input time-series signals x(n) are expressed in integers with a finite number of bits, and the linear prediction values y(n) are output values of a linear prediction filter with integer filter coefficients formed by rounding off or otherwise eliminating the fractional parts of the linear prediction coefficients. Then, each prediction residual e(n), which is obtained by subtracting the linear prediction value y(n) from the time-series signal x(n), is expressed in an integer form of a finite number of bits (or represented by an integer in a predetermined range). If the time-series signal x(n) or the linear prediction value y(n) is not expressed in an integer form, the prediction residual e(n) may be a value obtained by subtracting the linear prediction value y(n) from the time-series signal x(n) and converting the difference into an integer expression of a finite number of bits. The residual coding unit 2120 performs Golomb-Rice coding of the prediction residuals e(n) represented by integers. For example, in the Golomb-Rice coding, a Rice parameter calculator 2121 first generates a Rice parameter s, which is an integer, using the input one frame of prediction residuals e(n) (n=0, . . . , N−1). The Rice parameter s is a value that minimizes the total code amount of the codes corresponding to the one frame of prediction residuals e(n) (n=0, . . . , N−1), for example. In other words, the value of the Rice parameter s is associated with the magnitude of the input prediction residuals e(n). The Rice parameter s may be generated for each frame or each sub-frame, which is a time segment formed by dividing one frame.
Then, the prediction residuals e(n) and the Rice parameter s are input to a separating unit 2122a in a Golomb-Rice coding unit 2122. The separating unit 2122a performs a predetermined division using these values to calculate the integer quotients q(n) and information sub(n) that indicates the remainders. Essentially, the division is a calculation that divides the prediction residual e(n) by 2s. However, in order to separately handle positive and negative prediction residuals e(n) or reduce the code length, for example, the calculation that simply divides the prediction residual e(n) by 2s may be slightly modified. If the divisor is a power of 2, and the dividend is an integer expressed by a binary number, the division is a process of eliminating a lower-order bit of the dividend; higher-order bits represent the quotient, and the remaining lower-order bits represent the remainder.
Then, an Alpha coding unit 2122b performs alpha coding (which is variable length coding and referred to also as unary coding) of the quotient q(n) to generate information prefix(n) (a variable length code). The generated information prefix(n) and the information sub(n) are input to a combining unit 2122c. The combining unit 2122c outputs a bit combination value prefix(n)|sub(n) of the information prefix(n) and the information sub(n), the bit combination value being a residual code Ce corresponding to the prediction residual e(n) at a discrete time n. The residual coding unit 2120 also outputs a complementary code Cc that indicates the Rice parameter s along with the residual code Ce. When the Rice parameter s is generated for each frame, the information that indicates that sub-frame separation is not applied and the Rice parameter s are output as the complementary code Cc. When the Rice parameter s is generated for each sub-frame, the Rice parameter s generated for the first sub-frame, difference codes Cd obtained by performing Golomb-Rice coding of the differences between the Rice parameters s generated for adjacent sub-frames, and flag information indicating that the Rice parameter s is generated in each sub-frame are output as the complementary code Cc.
The coefficient code Ck generated by the prediction coding unit 2110, and the residual code Ce and the complementary code Cc generated by the residual coding unit 2120 are fed into a combining unit 2130, and the combining unit 2130 combines the codes to generate a code Cg.
(Decoding Method)
The code Cg input to the decoder 2200 is separated by a separator 2210 into the coefficient code Ck, the residual code Ce and the complementary code Cc. The coefficient code Ck is input to a prediction decoding unit 2230, and the residual code Ce and the complementary code Cc are input to the residual decoding unit 2220.
The residual decoding unit 2220 extracts the Rice parameter s from the input complementary code Cc. For example, when the complementary code Cc includes the flag information, the Rice parameters s for respective sub-frames are obtained by reproducing Rice parameters s for the second and following sub-frames in a Rice parameter reproducing unit 2222. Alternatively, when the complementary code Cc includes the information that indicates that the sub-frame separation is not applied, the Rice parameter s included in the complementary code Cc is the Rice parameter s for the frame. Besides, a Golomb-Rice decoding unit 2221 in the residual decoding unit 2220 separates the input residual code Ce into the information prefix(n) and the information sub(n). An alpha decoding unit 2221c decodes the separated information prefix(n) to generate the quotient q(n). Note that decoding of a variable length code is referred to as variable length decoding. The information sub(n), the quotient q(n) and the Rice parameter s are input to a combining unit 2221b, and the combining unit 2221b reproduces the prediction residual e(n) using these values.
The coefficient code Ck input to the prediction decoding unit 2230 is fed into a coefficient decoding unit 2231. The coefficient decoding unit 2231 decodes the coefficient code Ck to generate the quantized PARCOR coefficients i(m) (m=1, . . . , M) and outputs the generated quantized PARCOR coefficients i(m) (m=1, . . . , M). The quantized PARCOR coefficients i(m) (m=1, . . . , M) are fed into a linear prediction coefficient converter 2232. The linear prediction coefficient converter 2232 uses the quantized PARCOR coefficients i(m) (m=1, . . . , M) to calculate respective linear prediction coefficients α(m) (m=1, . . . , M) of the linear prediction filter of the prediction order M. A linear prediction unit 2233 generates linear prediction values y(n) (n=0, . . . , N−1) by applying the linear prediction filter having the calculated linear prediction coefficients α(m) (m=1, . . . , M) and up to one frame of time-series signals x(n) (n=0, . . . , N−1) previously output from an adder 2234. The adder 2234 sums the linear prediction values y(n) and the prediction residuals e(n) reproduced by the residual decoding unit 2220 to generate the time-series signals x(n) (an inverse prediction filtering processing). The process of generating the time-series signals x(n) (n=0, . . . , N−1) from the prediction residuals e(n) (n=0, . . . , N−1) is referred to as prediction synthesis, and the filter used for the process is referred to as a prediction synthesis filter. The prediction synthesis corresponding to the linear prediction analysis (short-term prediction analysis) is referred to as linear prediction synthesis (short-term prediction synthesis). The synthesis filter corresponding to the linear prediction filter is expressed by the following formula, for example:x(n)=e(n)−{α(1)·x(n−1)+α(2)·x(n−2)+ . . . +α(M)·x(n−M)}where α(1) to α(M) are coefficients of the synthesis filter in this example.
Although the coding method and the decoding method based on the linear prediction analysis are described above, there are the coding method and the decoding method based on the long-term prediction analysis, a combination of the short-term prediction analysis and the long-term prediction analysis or a multi-channel prediction analysis, which is a prediction analysis using an inter-channel correlation. The long-term prediction analysis is based on a property that the amplitude characteristics of time-series signals are repeated at a fundamental period. In the long-term prediction analysis, a long-term prediction model expressed by the following formula is defined.e(n)=x(n)+ρ(−tap)·x(n−τ+tap)+ . . . +ρ(tap)·x(n−τ−tap)  (3)This model is based on an assumption that the prediction residual e(n) is represented by a linear combination of a time-series signal x(n) at a time n and time-series signals x(n−τ−j) at a time n−τ−j preceding the time n by τ+j weighted with coefficients ρ(j) (referred to as a “gain”) (τ denotes a fundamental period (a delay value), and j=−tap, . . . , tap (tap is 0 or 1 in many cases)). Then, the gains ρ(j) (j=−tap, . . . , tap) and the delay values τ that minimize the energy corresponding to the one frame of prediction residuals e(n) are calculated for the input one frame of time-series signals x(n) (n=0, . . . , N−1). A linear FIR filter expressed by the following formula is referred to as a “long-term prediction filter”.y(n)=−{ρ(−tap)·x(n−τ+tap)+ . . . +ρ(tap)·x(n−τ−tap)}  (4)The prediction synthesis corresponding to the long-term prediction analysis is referred to as long-term prediction synthesis. The synthesis filter corresponding to the long-term prediction filter is expressed by the following formula, for example:x(n)=e(n)−{ρ(−tap)·x(n−τ+tap)+ . . . +ρ(tap)·x(n−τ−tap)}where ρ(−tap) to ρ(tap) are coefficients of the synthesis filter in this example.